package com.knights;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class knighsGraph {

	/**
	 * @param args
	 */
	private boolean adjMatrixBoolean[][];
	private int adjMatrixInt[][];
	private int vertexCount;

	public knighsGraph(int vertexcount) {
		this.vertexCount = vertexcount;

		adjMatrixBoolean = new boolean[vertexcount][vertexcount];
		adjMatrixInt = new int[vertexcount][vertexcount];
	}

	public void addEdgeBoolean(int i, int j) {
		if (i >= 0 && i < vertexCount && j >= 0 && j < vertexCount) {
			adjMatrixBoolean[i][j] = true;
			adjMatrixBoolean[j][i] = true;
		}
	}

	public void addEdgeInt(int i, int j, int count) {
		if (i >= 0 && i < vertexCount && j >= 0 && j < vertexCount) {
			adjMatrixInt[i][j] = count;
		}
	}

	public void increaseEdgeInt(int i, int j) {
		if (i >= 0 && i < vertexCount && j >= 0 && j < vertexCount) {
			adjMatrixInt[i][j]++;
		}
	}

	public void decreaseEdgeInt(int i, int j) {
		if (i >= 0 && i < vertexCount && j >= 0 && j < vertexCount) {
			if (adjMatrixInt[i][j] > 0)
				adjMatrixInt[i][j]--;
		}
	}

	public void removeEdgeInt(int i, int j) {
		if (i >= 0 && i < vertexCount && j >= 0 && j < vertexCount) {
			adjMatrixInt[i][j] = 0;
		}
	}

	public int edgeCount(int i, int j) {
		if (i >= 0 && i < vertexCount && j >= 0 && j < vertexCount) {
			return adjMatrixInt[i][j];
		}
		return 0;
	}

	public void removeEdgeBoolean(int i, int j) {
		if (i >= 0 && i < vertexCount && j >= 0 && j < vertexCount) {
			adjMatrixBoolean[i][j] = false;
			adjMatrixBoolean[j][i] = false;
		}
	}

	public boolean isEdgeBoolean(int i, int j) {
		if (i >= 0 && i < vertexCount && j >= 0 && j < vertexCount)
			return adjMatrixBoolean[i][j];
		else
			return false;
	}

	public static void main(String[] args) {
		
		System.out.println("Q.: draw a graph with 64 vertices representing \n " +
				"the square of a chessboard. join the vertices appropriately by edges, \n " +
				"each representing move of the knight. You will see that every vertex in \n " +
				"this graph has degree 2, 3, 4, 6, and 8. How many vertex are there of each type?");
		
		int vertexCount = 8;
		knighsGraph g1 = new knighsGraph(8);
		for (int i = 0; i < vertexCount; i++) {
			for (int j = 0; j < vertexCount; j++) {
				g1.addEdgeBoolean(i, j);
				g1.addEdgeInt(i, j, 0);
			}
		}

		for (int i = 0; i < vertexCount; i++) {
			for (int j = 0; j < vertexCount; j++) {
				if (g1.isEdgeBoolean(i - 2, j - 1)) {
					g1.increaseEdgeInt(i, j);
				}
				
				if (g1.isEdgeBoolean(i - 2, j + 1)) {
					g1.increaseEdgeInt(i, j);
				}
				if (g1.isEdgeBoolean(i + 2, j - 1)) {
					g1.increaseEdgeInt(i, j);
				}
				if (g1.isEdgeBoolean(i + 2, j + 1)) {
					g1.increaseEdgeInt(i, j);
				}
				
				if (g1.isEdgeBoolean(i - 1, j - 2)) {
					g1.increaseEdgeInt(i, j);
				}

				if (g1.isEdgeBoolean(i - 1, j + 2)) {
					g1.increaseEdgeInt(i, j);
				}
				if (g1.isEdgeBoolean(i + 1, j - 2)) {
					g1.increaseEdgeInt(i, j);
				}
				if (g1.isEdgeBoolean(i + 1, j + 2)) {
					g1.increaseEdgeInt(i, j);
				}
				
				

			}
		}
		
		
		System.out.println("Ans: Output of knights graphs as follow");
		System.out.println("");
		for (int i = 0; i < vertexCount; i++) {
			
			for (int j = 0; j < vertexCount; j++) {
				System.out.print("  ");
				System.out.print(g1.adjMatrixInt[i][j]);
				
			}
			System.out.println("");
		}
		
		
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		
		for (int i = 0; i < vertexCount; i++) {
			for (int j = 0; j < vertexCount; j++) {
				
				if(map.get(g1.adjMatrixInt[i][j]) != null)
					map.put(g1.adjMatrixInt[i][j], (map.get(g1.adjMatrixInt[i][j]))+1);
				else
					map.put(g1.adjMatrixInt[i][j], 1);
					
				
			}
			
		}
		System.out.println("");
		System.out.println("Vertex of each type as follow: ");
		 Set set = map.entrySet();
		 Iterator iter = set.iterator();
		 while (iter.hasNext()) {
		      Map.Entry entry = (Map.Entry) iter.next();
		      System.out.println(entry.getKey() + " -- " + entry.getValue());
		    }

	}

}
